Now that we have recursively split the original array $A$ into $n$ single-element, inherently sorted lists (the base cases), the core work of Merge Sort begins: the Combine (Merge) step.

  • The merge function takes two lists, $L$ (Left) and $R$ (Right), which are guaranteed to be individually sorted, and combines them into a single sorted output list $B$.
  • This process is achieved by maintaining two pointers, one for $L$ and one for $R$. In each step, we compare the elements pointed to and select the smaller one to append to the result $B$.
  • Since we only perform a comparison and a single copy operation (an $O(1)$ operation) for every element across $L$ and $R$ exactly once, the Merge operation takes linear time, $O(n)$, where $n$ is the combined size of the two input lists.
  • The total work done across all recursive calls at any single level of the recursion tree is always $O(n)$. Since there are $O(\log n)$ levels, the overall complexity remains $O(n \log n)$.
Python Implementation: merge
1def merge(Left, Right):
2    merged = []
3    i = j = 0 # Pointers for Left (i) and Right (j)
4    n_L, n_R = len(Left), len(Right)
5
6    # O(n) comparison loop
7    while i < n_L and j < n_R:
8        # Line 8: Comparison
9        if Left[i] <= Right[j]:
10            merged.append(Left[i])
11            i += 1 # Line 11
12        else:
13            merged.append(Right[j])
14            j += 1 # Line 14
15
16    # Append remaining elements (at most one loop executes)
17    merged.extend(Left[i:]) # Line 17
18    merged.extend(Right[j:]) # Line 18
19
20    return merged